struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    // 思路：使用双指针，先让右指针走n步，然后左指针和右指针同时走，直到右指针走到末尾，左指针的下一个节点就是要删除的节点
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *dummy = new ListNode(0, head); // 哨兵节点，防止删除头节点时出错
        ListNode *left = dummy;                  // 为什么不直接用head？因为可能删除的是头节点
        ListNode *right = head;                  // 右指针从head开始
        // 先让right跑n步，然后同时移动left和right直到right为空，left就是要删除的节点
        while (n && right) // right可能为空
        {
            right = right->next;
            --n;
        }
        // 同时移动left和right
        while (right)
        {
            left = left->next;
            right = right->next;
        }
        left->next = left->next->next;
        return dummy->next;
    }
};